#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-12-02 9:28 上午
# @Author  : yangdy
# @File    : 2020-12-02.321.拼接最大数
# @Software: PyCharmCE
from tools.my_methods import *


class Solution:
    def maxNumber(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
        ans = [0 for i in range(k)]
        for i in range(k+1):
            if i <= len(nums1) and k-i <= len(nums2):
                s1 = self.get_stack(nums1, i)
                s2 = self.get_stack(nums2, k-i)
                u = self.merge(s1, s2)
                if self.cmp(u, 0, ans, 0) > 0:
                    ans = u
        return ans

    def cmp(self, stack1, i1, stack2, i2):
        while i1 < len(stack1) and i2 < len(stack2):
            if stack1[i1] == stack2[i2]:
                i1, i2 = i1+1, i2+1
            else:
                return stack1[i1] - stack2[i2]
        return len(stack1) - i1 - len(stack2) + i2

    def merge(self, stack1, stack2):
        ans, i1, i2 = [], 0, 0
        while i1 < len(stack1) and i2 < len(stack2):
            if self.cmp(stack1, i1, stack2, i2) > 0:
                ans.append(stack1[i1])
                i1 += 1
            else:
                ans.append(stack2[i2])
                i2 += 1
        if i1 < len(stack1):
            ans.extend(stack1[i1:])
        elif i2 < len(stack2):
            ans.extend(stack2[i2:])
        return ans

    def get_stack(self, nums, k):
        stack, e = [], len(nums) - k
        for i in range(len(nums)):
            while len(stack) and e > 0 and stack[-1] < nums[i]:
                stack.pop()
                e -= 1
            if len(stack) < k:
                stack.append(nums[i])
            else:
                e -= 1
        return stack


questions = [
    ([3, 4, 6, 5], [9, 1, 2, 5, 8, 3], 5),
    ([6, 7], [6, 0, 4], 5),
    ([3, 9], [8, 9], 3),
    ([8, 6, 9], [1, 7, 5], 3),
]

work(questions, lambda q: Solution().maxNumber(q[0], q[1], q[2]))
